package com.lw.leetcode.arr.b;

/**
 * Created with IntelliJ IDEA.
 * arr
 * 424. 替换后的最长重复字符
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/6 10:09
 */
public class CharacterReplacement {

    public static void main(String[] args) {
        CharacterReplacement test = new CharacterReplacement();

        // 4
        String str = "ABAB";
        int k = 2;

        // 4
//        String str = "AABABBA";
//        int k = 1;

        int i = test.characterReplacement(str, k);
        System.out.println(i);
    }

    public int characterReplacement(String s, int k) {
        char[] arr = s.toCharArray();
        int max = 0;
        for (int i = 0; i < 26; i++) {
            max = Math.max(max, find(arr, (char) (i + 'A'), k));
        }
        return max;
    }

    private int find(char[] arr, char t, int k) {
        int max = 0;
        int length = arr.length;
        int st = 0;
        int s = 0;
        for (int end = 0; end < length; end++) {
            if (arr[end] != t) {
                s++;
                while (s > k) {
                    if (arr[st] != t) {
                        s--;
                    }
                    st++;
                }
            }
            max = Math.max(max, end - st + 1);
        }
        return max;
    }

}
